LeetCode 54. Spiral Matrix & 剑指Offer 29. 顺时针打印矩阵
解答1[Java]:
核心思想
从外层向内层,一圈一圈地遍历。
代码
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List ans = new ArrayList();
if (matrix.length == 0)
return ans;
int r1 = 0, r2 = matrix.length - 1;
int c1 = 0, c2 = matrix[0].length - 1;
while (r1 <= r2 && c1 <= c2) {
for (int c = c1; c <= c2; c++) ans.add(matrix[r1][c]);
for (int r = r1 + 1; r <= r2; r++) ans.add(matrix[r][c2]);
if (r1 < r2 && c1 < c2) {
for (int c = c2 - 1; c > c1; c--) ans.add(matrix[r2][c]);
for (int r = r2; r > r1; r--) ans.add(matrix[r][c1]);
}
r1++;
c1++;
r2--;
c2--;
}
return ans;
}
}
解答2[Java]:
核心思想
这个才是真的全自动顺时针打印。设计了两个数组,一个 directionOfRow,一个directionOfColumn,这样,directionOfRow[i] 和 directionOfColumn[i] 这么一组数就表示下一步该怎么走,如果越界了,那么 ++i,相当于换成下一种走法。第一圈使用数组行数和列数来判定是否越界,第二圈就要靠 seen 数组来判断。
代码
import java.util.ArrayList;
import java.util.List;
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> ans = new ArrayList();
if (matrix.length == 0) return ans;
int R = matrix.length, C = matrix[0].length;
boolean[][] seen = new boolean[R][C];
int[] directionOfRow = {0, 1, 0, -1};
int[] directionOfColumn = {1, 0, -1, 0};
int r = 0, c = 0, dierectionCount = 0;
for (int i = 0; i < R * C; ++i) {
ans.add(matrix[r][c]);
seen[r][c] = true;
int nextR = r + directionOfRow[dierectionCount];
int nextC = c + directionOfColumn[dierectionCount];
if (0 <= nextR && nextR < R && 0 <= nextC && nextC < C && !seen[nextR][nextC]) {
r = nextR;
c = nextC;
} else {
dierectionCount = (dierectionCount + 1) % 4;
r += directionOfRow[dierectionCount];
c += directionOfColumn[dierectionCount];
}
}
return ans;
}
}